package com.lims.algorithm.algset.backtracking.questions;

import org.apache.commons.lang3.StringUtils;

import java.util.*;
import java.util.stream.Stream;

/**
 * <描述:>电话号码组合——回溯法
 * 电话号码数字对应一个或多个字符，按下数字，求所有可能的字符串组合
 *
 * @author lims
 * @date 2020-09-13 18:06
 */
public class TelPhoneNumComb {
    /**
     * 电话号码组合
     */
    private Map<String, String[]> telNum;
    /**
     * 结果集
     */
    private List<String> resultCombs;
    /**
     * 辅助栈
     */
    private Stack<String> stack;

    public TelPhoneNumComb() {
        this.telNum = new HashMap<>();
        this.resultCombs = new ArrayList<>();
        this.stack = new Stack<>();

        telNum.put("2", new String[]{"a", "b", "c"});
        telNum.put("3", new String[]{"d", "e", "f"});
        telNum.put("4", new String[]{"g", "h", "i"});
        telNum.put("5", new String[]{"j", "k", "l"});
        telNum.put("6", new String[]{"m", "n", "o"});
        telNum.put("7", new String[]{"p", "q", "r", "s"});
        telNum.put("8", new String[]{"t", "u", "v"});
        telNum.put("9", new String[]{"w", "x", "y", "z"});
    }

    /**
     * 回溯法处理函数
     */

    public List<String> comDFS(String digitals) {
        if (digitals.length() > 0) {
            char[] chars = digitals.toCharArray();
            String[] sa = new String[chars.length];
            Stream.iterate(0, t -> t + 1).limit(chars.length)
                    .forEach(i -> {
                        sa[i] = new String(chars, i, 1);
                    });
            combDFS(0, sa);
        }
        return resultCombs;
    }

    private void combDFS(int index, String[] digitals) {
        if (index == digitals.length) {
            String s = StringUtils.EMPTY;
            Stack<String> tmpStack = new Stack<>();
            while (!stack.isEmpty()) {
                String pop = stack.pop();
                tmpStack.push(pop);
            }
            while (!tmpStack.isEmpty()) {
                String pop = tmpStack.pop();
                s = s.concat(pop);
                stack.push(pop);
            }
            resultCombs.add(s);
            return;
        }

        for (int i = 0; i < telNum.get(digitals[index]).length; ++i) {
            stack.push(telNum.get(digitals[index])[i]);
            combDFS(index + 1, digitals);
            stack.pop();
        }
    }

    /**************************/
    public static void main(String[] args) {
        TelPhoneNumComb numComb = new TelPhoneNumComb();
        List<String> list = numComb.comDFS("23");
        System.out.println(list);
    }
}
